package com.sicheng.蓝桥.练习题.基础图论.最小生成树;

import java.util.*;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/12 17:26
 */
public class 使用堆和领接表优化迪杰斯特拉 {

    //4 5
    //1 2 1
    //1 3 2
    //1 4 3
    //2 3 2
    //3 4 4
    static Map<Integer, Set<int[]>> g;//存储图
    //存储到生成树的距离，和点的编号
    static PriorityQueue<int[]> heap;

    static boolean[] st;
    static long[] dist;

    //fixme  这个板子不好 待完善 可以看网络延迟时间那道题 在哪有完善版的板子
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        heap = new PriorityQueue<>(Comparator.comparingInt(e -> e[0]));
        st = new boolean[n + 1];
        dist = new long[n + 1];
        g = new HashMap<>();
        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int l = scanner.nextInt();
            add(x, y, l);
            add(y, x, l);
        }

        long max = Long.MAX_VALUE >> 4;
        Arrays.fill(dist, max);
        //首先把一号结点纳入
        heap.add(new int[]{0, 1});
        dist[1] = 0;
        int t = 0;
        while (!heap.isEmpty()) {
            int[] top = heap.remove();
            t = top[1];
            if (st[t])
                continue;
            st[t] = true;
            Set<int[]> set = g.get(t);
            if (set != null) {
                for (int[] d : set) {
                    if (dist[t] + d[0] < dist[d[1]]) {
                        dist[d[1]] = dist[t] + d[0];
                        heap.add(d);
                    }
                }
            }
        }
        if (dist[t] >= max)
            System.out.println("-1");
        System.out.println(dist[t]);

    }

    private static void add(int a, int b, int l) {
        Set<int[]> set = g.computeIfAbsent(a, k -> new HashSet<>());
        set.add(new int[]{l, b});
    }
}
